package search;

import com.sun.net.httpserver.Authenticator;

import java.nio.file.NotDirectoryException;
import java.util.LinkedList;

public class BinarySearchTree {
    private Integer count;
    private Node root;


    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(46, 2);
        binarySearchTree.insert(33, 3);
        binarySearchTree.insert(72, 3);
        binarySearchTree.insert(16, 3);
        binarySearchTree.insert(44, 3);
        binarySearchTree.insert(50, 3);
        binarySearchTree.insert(80, 3);
        binarySearchTree.insert(47, 3);
        binarySearchTree.insert(45, 3);
        System.out.println(binarySearchTree.contain(35));
        System.out.println(binarySearchTree.search(33));
        binarySearchTree.beforeForEach();
        binarySearchTree.midForEach();
        binarySearchTree.afterForEach();
        binarySearchTree.wideForEach();
        System.out.println("///");
        System.out.println(binarySearchTree.minium());
        System.out.println(binarySearchTree.maxium());
        Node node = binarySearchTree.floor(45);
        System.out.println(node.index);
        node = binarySearchTree.ceil(44);
        System.out.println(node.index);

    }

    public Node floor(int exp) {
        return floor(root, exp);
    }

    public Node floor(Node node, int exp) {
        if (node == null) {
            return null;
        }
        if (exp < node.index) {
            return floor(node.left, exp);
        }
        Node tempNode = floor(node.right, exp);
        if (tempNode != null) {
            return tempNode;
        }
        return node;
    }

    public Node ceil(int exp) {
        return ceil(root, exp);
    }

    public Node ceil(Node node, int exp) {

        if (node == null) {
            return null;
        }
        System.out.println(node.index);
        if (exp > node.index) {
            return ceil(node.right, exp);
        }
        Node tempNode = ceil(node.left, exp);
        if (tempNode != null) {
            return tempNode;
        }
        return node;
    }


    public Node remove(Node node, int index) {
        //node
        if (node == null) {
            return null;
        }
        //假如index<当前index往左走
        if (index < node.index) {
            node.left = remove(node.left, index);
            return node;
        } else if (index > node.index) {
            node.right = remove(node.right, index);
            return node;
        }
        Node successor = new Node(minium(node.right));
        count++;
        successor.right = removeMin(node.right);
        successor.left = node.left;
        node.left = node.right = null;
        count--;
        return successor;

    }

    public Node minium() {
        return minium(root);
    }

    public Node maxium() {
        return maxium(root);
    }

    public void removeMin() {
        if (root != null) {
            root = removeMin(root);
        }
    }


    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            count--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public void removeMax() {
        if (root != null) {
            root = removeMax(root);
        }
    }


    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            count--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public Node minium(Node node) {
        if (node.left != null) {
            return minium(node.left);
        } else {
            return node;
        }
    }

    public Node maxium(Node node) {
        if (node.right != null) {
            return maxium(node.right);
        } else {
            return node;
        }
    }

    public void wideForEach() {
        LinkedList<Node> nodeLinkedList = new LinkedList<>();
        //将整棵树放入双向链表中
        nodeLinkedList.add(root);
        int i = count;
        while (!nodeLinkedList.isEmpty()) {
            //从链表中移除该节点，并返回该节点
            Node node = nodeLinkedList.remove();
            System.out.println(node.index);
            if (node.left != null) {
                //添加左节点
                nodeLinkedList.add(node.left);
            }
            if (node.right != null) {
                //添加右节点
                nodeLinkedList.add(node.right);
            }
        }
    }

    //   1
    //  2 3
    //4 5 6 7
    public void beforeForEach() {
        beforeForEach(root);
        System.out.println("//");
    }


    //中序遍历
    public void midForEach() {
        midForEach(root);
        System.out.println("//");
    }

    //后序遍历
    public void afterForEach() {
        afterForEach(root);
        System.out.println("//");
    }

    //前序遍历
    public void beforeForEach(Node node) {
        if (node != null) {
            System.out.println(node.index);
            beforeForEach(node.left);
            beforeForEach(node.right);
        }
    }

    //中序遍历
    public void midForEach(Node node) {
        if (node != null) {

            midForEach(node.left);
            System.out.println(node.index);
            midForEach(node.right);
        }
    }

    //后序遍历
    public void afterForEach(Node node) {
        if (node != null) {

            afterForEach(node.left);
            afterForEach(node.right);
            System.out.println(node.index);
        }
    }

    //初始化二叉搜索树
    private BinarySearchTree() {
        root = null;
        count = 0;
    }

    public boolean contain(int idx) {
        return contain(root, idx);
    }

    public boolean contain(Node node, int idx) {
        if (node == null) {
            return false;
        }
        if (node.index == idx) {
            return true;
        } else if (idx < node.index) {
            return contain(node.left, idx);
        } else {
            return contain(node.right, idx);
        }


    }

    public int search(int idx) {
        return search(root, idx);
    }


    public int search(Node node, int idx) {

        if (node == null) {
            return -1;
        }
        //root
        if (idx == node.index) {
            return node.value;
        } else if (idx < node.index) {
            return search(node.left, idx);
        } else {
            return search(node.right, idx);
        }


    }


    private void insert(Integer key, Integer val) {
        root = insert(root, key, val);
    }

    private Node insert(Node node, int index, int val) {
        if (node == null) {
            count++;
            return new Node(index, val);
        }

        if (index < node.index) {
            node.left = insert(node.left, index, val);

        } else if (index > node.index) {
            node.right = insert(node.right, index, val);

        }
        return node;


    }

    class Node {
        Integer index;
        Integer value;
        Node left;
        Node right;

        Node(Node node) {
            this.index = node.index;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
        }

        Node(Integer index, Integer value) {
            this.index = index;
            this.value = value;
        }
    }
}
